#coding: utf-8

SYSREGS=['RS', 'RC0']
COPS=['EQ','NE','GT','GE','LT','LE','ET','OU','NON','VRAI','FAUX']

class CompileError(Exception):
  def __init__(self,str):
    self.str=str
  def __str__(self):
    return self.str

class ParseError(CompileError):
  pass

def compile(tok,achk=True):
  return parser().compile(tok,achk)

class CON:
  def __init__(self,n):
    self.cnum=n

class code(list):
  def __init__(self):
    list.__init__(self)
    self.cnum=0

  def addCON(self,k=0):
    out=[]
    k+=self.cnum
    for a in self:
      if isinstance(a,code):
        out.extend(a.addCON(k))
      elif isinstance(a,CON):
        out.append(k+a.cnum)
      else:
        out.append(a)
    return out

def macro_a(s):
  return 'A%s' % s

def macro_as(s):
  return 'AS%s' % s

def label_fid(s):
  return 'L!%s' % s

def label_lab(f,l):
  return '%s@%s' % (label_fid(f),l)

class parser:
  def label_next(self):
    if hasattr(self,'lab_n'):
      self.lab_n+=1
    else:
      self.lab_n=0
    return 'L%s' % self.lab_n

  def ttype(self,n=0):
    if n<len(self.tok):
      return self.tok[n][0]

  def perror(self):
    t=self.ttype()
    if t:
      raise ParseError('parse error at %s' % t)
    else:
      raise ParseError('cannot get next token')

  def shiftok(self):
    self.tok=self.tok[1:]

  def chktok(self,type):
    t=self.ttype()
    if t!=type:
      self.perror()
    if t:
      ret=self.tok[0][1]
      self.shiftok()
      return ret

  def sep(self):
    t=self.ttype()
    if t=='NL':
      self.shiftok()
    elif t=='SEMI':
      self.shiftok()
      self.ttype()=='NL' and self.shiftok()
    else:
      self.perror()

  def compile(self,tok,achk):
    self.tok=tok
    self.achk=achk
    self.gvars={}
    self.funcs={}
    self.arrs={}
    self.macros=dict([(SYSREGS[i],i) for i in range(len(SYSREGS))])

    dcode=code()
    while True:
      t=self.ttype()
      if t=='FUNCTION':
        dcode.append(self.fdecl())
      elif t=='ARRAY':
        self.adecl()
      else:
        break

    self.lvars={}
    self.ln=0
    self.fid='MAIN'
    self.tlabs={}
    mcode=self.t()
    if len(self.tok)!=0:
      self.perror()

    for k,v in self.funcs.iteritems():
      if not v[1]:
        raise CompileError('function %s is not defined' % k)

    for k,v in self.tlabs.iteritems():
      if not v:
        raise CompileError('label %s is not defined in %s' % (k,self.fid))

    acode=code()
    for k,v in self.arrs.iteritems():
      if v==None:
        raise CompileError("array %s is not declared" % k)
      self.macros[macro_a(k)]=len(SYSREGS)+len(self.gvars)+len(acode)-1
      self.macros[macro_as(k)]=len(v)
      acode.extend(v)

    l=label_fid(self.fid)
    rcode=code()
    rcode.append(['sal',len(SYSREGS)+len(self.gvars)])
    rcode.append(acode)
    rcode.append(['jmp',l])
    rcode.append(dcode)
    rcode.append(['lab',l])
    rcode.append(len(SYSREGS)+len(self.gvars)+len(acode))
    rcode.append(['gto','RS'])
    rcode.append(['sal',len(self.lvars)])
    mcode.cnum+=len(self.lvars)
    rcode.append(mcode)
    rcode.append(['hal',0])

    return (rcode.addCON(), self.macros)

  def fdecl(self):
    self.chktok('FUNCTION')
    self.fid=self.chktok('ID')
    self.lvars={}
    self.ln=0
    self.tlabs={}
    self.chktok('LPAR')
    pnum=self.args()
    self.chktok('RPAR')
    self.sep()
    bo=self.t()
    self.chktok('END')
    self.sep()

    for k,v in self.tlabs.iteritems():
      if not v:
        raise CompileError('label %s is not defined in %s' % (k, self.fid))

    if self.fid in self.funcs:
      a=self.funcs[self.fid]
      if a[1]:
        raise CompileError('function %s is already defined' % self.fid)
      if a[0]!=pnum:
        raise CompileError("argument number error (%s)" % self.fid)
      a[1]=True
    else:
      self.funcs[self.fid]=[pnum,True]

    ret=code()
    ret.append(['lab',label_fid(self.fid)])
    w=len(self.lvars)-1-pnum
    ret.append(['sal',w])
    bo.cnum+=w
    ret.append(bo)
    ret.append(['pop',len(self.lvars)-1])
    ret.extend([['gto',i] for i in reversed(SYSREGS)])
    ret.append('jpo')
    return ret

  def args(self):
    if self.ttype()!='ID':
      self.lvars[self.fid]=-(3+len(SYSREGS))
      return 0

    a=[]
    while True:
      id=self.chktok('ID')
      if id==self.fid or id in a:
        raise CompileError("variable %s already exists" % id)
      a.append(id)
      if self.ttype()=='COMMA':
        self.shiftok()
        continue
      break

    self.lvars.update([(a[i],i-len(a)) for i in range(len(a))])
    self.lvars[self.fid]=-(3+len(SYSREGS)+len(a))
    return len(a)

  def adecl(self):
    self.chktok('ARRAY')
    id=self.chktok('ID')
    if id in self.arrs and self.arrs[id]!=None:
      raise CompileError("array %s is already declared" % id)

    t=self.ttype()
    if t=='LBRA':
      self.shiftok()
      k=self.anum()
      if k<=0:
        raise CompileError('array size must be positive')
      self.arrs[id]=[0]*k
      self.chktok('RBRA')
      self.sep()
    elif t=='DEF':
      self.shiftok()
      self.chktok('LBRA')
      a=self.arrs[id]=[self.anum()]
      while self.ttype()=='COMMA':
        self.shiftok()
        a.append(self.anum())
      self.chktok('RBRA')
      self.sep()
    else:
      self.perror()

  def anum(self):
    t=self.ttype()
    if t=='PLUS':
      self.shiftok()
      return self.chktok('NUM')
    elif t=='MINUS':
      self.shiftok()
      return -self.chktok('NUM')
    else:
      return self.chktok('NUM')

  def chkaind(self,id):
    if not self.achk:
      return code()

    l0,l1=self.label_next(),self.label_next()
    ret=code()
    ret.append(['gto','RC0'])
    ret.append(['god','RC0'])
    ret.append(['jpo',l1])
    ret.append(['lab',l0])
    ret.append(['hal',1])
    ret.append(['lab',l1])
    ret.append(['god','RC0'])
    ret.append(macro_as(id))
    ret.append('sub')
    ret.append(['jpo',l0])
    ret.append(['god','RC0'])
    return ret

  def t(self):
    ret=code()
    while True:
      t=self.ttype()
      if t=='WRITE':
        ret.append(self.writes())
      elif t=='ID':
        ret.append(self.proc() if self.ttype(1)=='LPAR' else self.dain())
      elif t=='DOLLAR':
        ret.append(self.dain())
      elif t=='READ':
        ret.append(self.reads())
      elif t=='IF':
        ret.append(self.ifs())
      elif t=='WHILE':
        ret.append(self.whiles())
      elif t=='GOTO':
        ret.append(self.gotos())
      elif t=='LABEL':
        ret.append(self.labels())
      else:
        break
    return ret

  def proc(self):
    ret=self.func()
    self.sep()
    ret.append('pop')
    return ret

  def writes(self):
    self.chktok('WRITE')
    ret=self.e()
    self.sep()
    ret.append('pri')
    return ret

  def whiles(self):
    self.chktok('WHILE')
    co=self.conds()
    self.sep()
    bo=self.t()
    self.chktok('END')
    self.sep()

    l0,l1=self.label_next(),self.label_next()
    ret=code()
    ret.append(['lab',l0])
    ret.append(co)
    ret.append(['jpo',l1])
    ret.append(bo)
    ret.append(['jmp',l0])
    ret.append(['lab',l1])
    return ret

  def gotos(self):
    self.chktok('GOTO')
    id=self.chktok('ID')
    self.sep()
    if id not in self.tlabs:
      self.tlabs[id]=False
    ret=code()
    ret.append(['jmp',label_lab(self.fid,id)])
    return ret

  def labels(self):
    self.chktok('LABEL')
    id=self.chktok('ID')
    self.sep()
    if id in self.tlabs and self.tlabs[id]:
      raise CompileError('label %s is already appeared in %s' % (id, self.fid))
    self.tlabs[id]=True
    ret=code()
    ret.append(['lab',label_lab(self.fid,id)])
    return ret

  def dain(self):
    if self.ttype()=='DOLLAR':
      self.shiftok()
      id=self.chktok('ID')
      self.chktok('DEF')
      ret=self.e()
      self.sep()

      if id not in self.gvars:
        self.gvars[id]=len(SYSREGS)+len(self.gvars)
      ret.append(['gto',self.gvars[id]])
      return ret

    id=self.chktok('ID')
    t=self.ttype()
    if t=='DEF':
      self.shiftok()
      ret=self.e()
      self.sep()

      if id not in self.lvars:
        self.lvars[id]=self.ln
        self.ln+=1
      ret.append(self.lvars[id])
      ret.append(['god','RS'])
      ret.append('add')
      ret.append('gto')
    elif t=='LBRA':
      self.shiftok()
      ind=self.e()
      self.chktok('RBRA')
      self.chktok('DEF')
      ret=self.e()
      self.sep()

      if id not in self.arrs:
        self.arrs[id]=None
      ret.append(macro_a(id))
      ind.cnum+=2
      ret.append(ind)
      ret.append(self.chkaind(id))
      ret.append('add')
      ret.append('gto')
    else:
      self.perror()
    return ret

  def reads(self):
    self.chktok('READ')
    if self.ttype()=='DOLLAR':
      self.shiftok()
      id=self.chktok('ID')
      self.sep()

      if id not in self.gvars:
        self.gvars[id]=len(SYSREGS)+len(self.gvars)
      ret=code()
      ret.append('red')
      ret.append(['gto',self.gvars[id]])
      return ret

    id=self.chktok('ID')
    if self.ttype()=='LBRA':
      self.shiftok()
      ind=self.e()
      self.chktok('RBRA')
      self.sep()

      if id not in self.arrs:
        self.arrs[id]=None
      ret=code()
      ret.append('red')
      ret.append(macro_a(id))
      ind.cnum+=2
      ret.append(ind)
      ret.append(self.chkaind(id))
      ret.append('add')
      ret.append('gto')
    else:
      self.sep()
      if id not in self.lvars:
        self.lvars[id]=self.ln
        self.ln+=1
      ret=code()
      ret.append('red')
      ret.append(self.lvars[id])
      ret.append(['god','RS'])
      ret.append('add')
      ret.append('gto')
    return ret

  def ifs(self):
    self.chktok('IF')
    ret=self.conds()
    self.sep()
    bo=self.t()

    lend,l=self.label_next(),self.label_next()
    ret.append(['jpo',l])
    ret.append(bo)
    ret.append(['jmp',lend])
    ret.append(['lab',l])

    while self.ttype()=='ELSIF':
      self.shiftok()
      co=self.conds()
      self.sep()
      bo=self.t()

      l=self.label_next()
      ret.append(co)
      ret.append(['jpo',l])
      ret.append(bo)
      ret.append(['jmp',lend])
      ret.append(['lab',l])

    t=self.ttype()
    if t=='ELSE':
      self.shiftok()
      self.sep()
      bo=self.t()
      self.chktok('END')
      self.sep()

      ret.append(bo)
      ret.append(['lab',lend])
    elif t=='END':
      self.shiftok()
      self.sep()
      ret.append(['lab',lend])
    else:
      self.perror()
    return ret

  def conds(self):
    ret=self.et()
    while self.ttype()=='OU':
      self.shiftok()
      c=self.et()
      l1,l2=self.label_next(),self.label_next()
      ret.append(['jpo',l1])
      ret.append(0)
      ret.append(['jmp',l2])
      ret.append(['lab',l1])
      ret.append(c)
      ret.append(['lab',l2])
    return ret

  def et(self):
    ret=self.cond()
    while self.ttype()=='ET':
      self.shiftok()
      c=self.cond()
      l1,l2=self.label_next(),self.label_next()
      ret.append(['jpo',l1])
      ret.append(c)
      ret.append(['jmp',l2])
      ret.append(['lab',l1])
      ret.append(1)
      ret.append(['lab',l2])
    return ret

  def cond(self):
    tt=self.ttype()
    if tt=='LPAR':
      p=1
      for q in range(1,len(self.tok)):
        t=self.ttype(q)
        if t in COPS:
          self.shiftok()
          ret=self.conds()
          self.chktok('RPAR')
          return ret
        elif t=='LPAR':
          p+=1
        elif t=='RPAR':
          p-=1
          if p==0:
            break
      else:
        self.perror()
    elif tt=='NON':
      self.shiftok()
      v=self.cond()
      ret=code()
      ret.append(1)
      v.cnum+=1
      ret.append(v)
      ret.append('sub')
      return ret
    elif tt=='VRAI':
      self.shiftok()
      ret=code()
      ret.append(0)
      return ret
    elif tt=='FAUX':
      self.shiftok()
      ret=code()
      ret.append(1)
      return ret

    e1=self.e()
    op=self.ttype()
    if op not in COPS:
      self.perror()
    self.shiftok()
    e2=self.e()

    if op=='EQ':
      ret=e1
      l1,l2=self.label_next(),self.label_next()
      e2.cnum+=1
      ret.append(e2)
      ret.append('sub')
      ret.append(['gto','RC0'])
      ret.append(['god','RC0'])
      ret.append(['jpo',l1])
      ret.append(0)
      ret.append(['god','RC0'])
      ret.append('sub')
      ret.append(['jmp',l2])
      ret.append(['lab',l1])
      ret.append(1)
      ret.append(['lab',l2])
    elif op=='NE':
      ret=e1
      l1,l2=self.label_next(),self.label_next()
      e2.cnum+=1
      ret.append(e2)
      ret.append('sub')
      ret.append(['gto','RC0'])
      ret.append(['god','RC0'])
      ret.append(['jpo',l1])
      ret.append(['god','RC0'])
      ret.append(1)
      ret.append('add')
      ret.append(['jmp',l2])
      ret.append(['lab',l1])
      ret.append(0)
      ret.append(['lab',l2])
    elif op=='GT':
      ret=e2
      e1.cnum+=1
      ret.append(e1)
      ret.append('sub')
      ret.append(1)
      ret.append('add')
    elif op=='GE':
      ret=e2
      e1.cnum+=1
      ret.append(e1)
      ret.append('sub')
    elif op=='LT':
      ret=e1
      e2.cnum+=1
      ret.append(e2)
      ret.append('sub')
      ret.append(1)
      ret.append('add')
    elif op=='LE':
      ret=e1
      e2.cnum+=1
      ret.append(e2)
      ret.append('sub')
    return ret

  def e(self):
    ret=self.f()
    while True:
      t=self.ttype()
      if t=='PLUS':
        self.shiftok()
        v=self.f()
        v.cnum+=1
        ret.append(v)
        ret.append('add')
      elif t=='MINUS':
        self.shiftok()
        v=self.f()
        v.cnum+=1
        ret.append(v)
        ret.append('sub')
      else:
        break
    return ret

  def f(self):
    ret=self.g()
    while True:
      t=self.ttype()
      if t=='MUL':
        self.shiftok()
        v=self.g()
        v.cnum+=1
        ret.append(v)
        ret.append('mul')
      elif t=='DIV':
        self.shiftok()
        v=self.g()
        v.cnum+=1
        ret.append(v)
        ret.append('div')
      elif t=='MOD':
        self.shiftok()
        v=self.g()
        ret.append(['gto','RC0'])
        ret.append(['god','RC0'])
        ret.append(['god','RC0'])
        v.cnum+=2
        ret.append(v)
        ret.append(['gto','RC0'])
        ret.append(['god','RC0'])
        ret.append('div')
        ret.append(['god','RC0'])
        ret.append('mul')
        ret.append('sub')
      else:
        break
    return ret

  def g(self):
    t=self.ttype()
    if t=='NUM':
      v=self.chktok('NUM')
      ret=code()
      ret.append(v)
    elif t=='PLUS':
      self.shiftok()
      ret=self.g()
    elif t=='MINUS':
      self.shiftok()
      v=self.g()
      if len(v)==1 and isinstance(v[0], (int,long)):
        v[0]=-v[0]
        ret=v
      else:
        v.cnum+=1
        ret=code()
        ret.append(0)
        ret.append(v)
        ret.append('sub')
    elif t=='DOLLAR':
      self.shiftok()
      id=self.chktok('ID')
      if id not in self.gvars:
        self.gvars[id]=len(SYSREGS)+len(self.gvars)
      ret=code()
      ret.append(['god',self.gvars[id]])
    elif t=='PIPE':
      self.shiftok()
      id=self.chktok('ID')
      self.chktok('PIPE')
      if id not in self.arrs:
        self.arrs[id]=None
      ret=code()
      ret.append(macro_as(id))
    elif t=='LPAR':
      self.shiftok()
      ret=self.e()
      self.chktok('RPAR')
    elif t=='ID':
      t1=self.ttype(1)
      if t1=='LPAR':
        ret=self.func()
      elif t1=='LBRA':
        id=self.chktok('ID')
        self.chktok('LBRA')
        ind=self.e()
        self.chktok('RBRA')

        if id not in self.arrs:
          self.arrs[id]=None
        ret=code()
        ret.append(macro_a(id))
        ind.cnum+=1
        ret.append(ind)
        ret.append(self.chkaind(id))
        ret.append('add')
        ret.append('god')
      else:
        id=self.chktok('ID')
        if id not in self.lvars:
          self.lvars[id]=self.ln
          self.ln+=1
        ret=code()
        ret.append(self.lvars[id])
        ret.append(['god','RS'])
        ret.append('add')
        ret.append('god')
    else:
      self.perror()
    return ret

  def func(self):
    id=self.chktok('ID')
    self.chktok('LPAR')
    p=self.params()
    self.chktok('RPAR')

    pnum=len(p)
    if id not in self.funcs:
      self.funcs[id]=[pnum,False]
    elif pnum!=self.funcs[id][0]:
      raise CompileError('argument number error (%s)' % id)

    l0=self.label_next()
    ret=code()
    ret.append(0)
    ret.append(1)
    ret.append(l0)
    ret.extend([['god',j] for j in SYSREGS])
    ret.append(p)
    ret.append(['god','RS'])
    ret.append(CON(3+len(SYSREGS)+pnum))
    ret.append('add')
    ret.append(['gto','RS'])
    ret.append(['jmp',label_fid(id)])
    ret.append(['lab',l0])
    return ret

  def params(self):
    if self.ttype()=='RPAR':
      return code()
    ret=code()
    ret.cnum=3+len(SYSREGS)
    while True:
      v=self.e()
      v.cnum+=len(ret)
      ret.append(v)
      if self.ttype()!='COMMA':
        break
      else:
        self.shiftok()
    return ret
